package com.shuang.dp22;

class Solution {
    //打家劫舍问题 将第一个和最后一个房屋连在一起了 即分两种情况讨论 第一种考虑包含首元素不包含尾元素 第二种考虑不包含首包含尾 两种取最大
    public int rob(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return nums[0];
        }

        return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
    }

    //打家劫舍实现 索引开始位置包左不包右
    private int robAction(int[] nums, int start, int end) {

        //使用三个数用来替代dp数组 实现递推 初始化为0 遍历时直接从start开始相当于在开始位置前面补零
        int x = 0, y = 0, z = 0;

        //遍历
        for (int i = start; i < end; i++) {
            z = Math.max(x + nums[i], y);
            x = y;
            y = z;
        }

        return z;
    }
}